//
// Created by pangy on 2025/5/11.
//

#include "DuLinkList.h"

/*---------------------------------链表常规操作------------------------*/
/**
 * 构造一个空的双向循环链表 L
 * 成功返回OK,失败返回ERROR
*/
Status InitList(DuLinkList* L) {
    // 分配头结点
    *L =  (DuLinkList)malloc(sizeof(DuLNode));

    // 空间分配失败
    if (*L == NULL) {
        exit(OVERFLOW);
    }

    (*L)->prior = (*L)->next = *L;

    return OK;
}

/**
 * 销毁线性表
 * 成功返回OK, 失败返回ERROR
 * */
Status DestroyList(DuLinkList* L) {
    // 验证线性表存在
    if (L == NULL || *L == NULL) {
        return ERROR;
    }

    ClearList(*L);

    free(*L);

    *L = NULL;

    return OK;
}

/**
 * 清空线性表, 释放原链表的节点空间
 * 成功返回OK,失败返回ERROR
*/
Status ClearList(DuLinkList L) {
    DuLinkList p, q;

    if (L == NULL) {
        return ERROR;
    }

    p = L->next;

    while (p != L) {
        q = p->next;
        free(p);
        p = q;
    }

    L->next = L->prior = L;

    return OK;

}

/**
 * 线性表判空
 * 空表返回TRUE, 否则返回FALSE
 * */
Boolean ListEmpty(DuLinkList L) {
    if (L == NULL) {
        return FALSE;
    }
    return L->next == L && L->prior == L;
}

/**
 * 线性表长度
 * 返回线性表长度, 空表返回0
 * */
int ListLength(DuLinkList L) {
    int i;
    DuLinkList p;

    if (L == NULL || L->next == L || L->prior == L) {
        return 0;
    }

    i = 0;
    p = L->next;

    while (p != L) {
        i++;
        p = p->next;
    }

    return i;
}

/**
 * 返回链表中第一个满足compare条件的结点
 * @param L 链表
 * @param e 数据元素值
 * @param Compare 比较函数
 * @return 结点
 */
int LocateElem(DuLinkList L, ElemType e, Status (Compare)(ElemType, ElemType)) {
    int j;
    DuLinkList p;

    // 双向链表判空
    if (L == NULL || L->next == L || L->prior == L) {
        return 0;
    }

    p = L;
    j = 0;

    while (p->next != L && !Compare(p->data, e)) {
        p = p->next;
        j++;
    }

    if (p != L) {
        return j;
    } else {
        return 0;
    }
}

/**
 * 在指定位置之前插入数据元素
 * @param L 线性表
 * @param i 指定位置
 * @param e 插入数据元素
 * @return OK/ERROR
 */
Status ListInsert(DuLinkList* L, int i, ElemType e) {
    DuLinkList p, s;

    if (!(p = GetElemP(*L, i))) {
        return ERROR;
    }

    if (!(s = (DuLinkList) malloc(sizeof(DuLNode)))) {
        exit(OVERFLOW);
    }

    s->data = e;
    s->prior = p->prior;
    s->next = p;
    p->prior->next = s;
    p->prior = s;

    return OK;
}

/**
 * 删除指定位置的数据元素
 * @param L 线性表
 * @param i 位置
 * @param e 删除的数据元素
 * @return OK/ERROR
 */
Status ListDelete(DuLinkList* L, int i, ElemType* e) {
    DuLinkList p, s;

    if (!(p = GetElemP(*L, i))) {
        return ERROR;
    }

    *e = p->data;

    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);

    return OK;
}

/**
 * 线性表数据元素依次操作
 * @param L 线性表
 * @param Visit 操作函数
 */
void ListTraverse(DuLinkList L, void (*visit)(ElemType)) {
    DuLinkList  p;

    if (L == NULL || L->next == L || L->prior == L) {
        return;
    }

    p = L->next;

    while (p != L) {
        visit(p->data);
        p = p->next;
    }
}

/**
 * 返回指定结点的前驱
 * @param L
 * @param p
 * @return
 */
Status PriorElem(DuLinkList L, ElemType cur_e, ElemType* pre_e) {
    DuLinkList p;

    // 校验双向链表非空
    if (L == NULL || L->next == L || L->prior == L) {
        return ERROR;
    }

    p = L->next;

    // 遍历链表,找到指定节点
    while (p != L && p->data != cur_e) {
        p = p->next;
    }

    // 遍历未匹配或第一个元素没有前驱
    if (p == L || p->prior == L) {
        return ERROR;
    }

    // 指定结点前驱赋值给pre_e
    *pre_e = p->prior->data;

    return OK;
}

/**
 * 返回指定结点的后继
 * @param L
 * @param p
 * @return
 */
Status NextPos(DuLinkList L, ElemType cur_e, ElemType* next_e) {
    DuLinkList p;

    // 校验双向链表非空
    if (L == NULL || L->next == L || L->prior == L) {
        return ERROR;
    }

    p = L->next;
    while (p->next != L && p->data != cur_e) {
        p = p->next;
    }

    if (p->next == L) {
        return ERROR;
    }

    *next_e = p->next->data;

    return OK;
}


/**
 * 获取L中第i个元素的值,赋值到e中
 * @param L
 * @param i
 * @param e
 * @return
 */
Status GetElem(DuLinkList L, int i, ElemType* e) {
    int j;
    DuLinkList p;

    // 判断双向链表是否为空
    if (L == NULL || L->next == L || L->prior == L) {
        return ERROR;
    }

    j = 0;
    p = L;

    while (p->next != L && j < i) {
        p = p->next;
        j++;
    }

    if (p->next == L || j > i) {
        return ERROR;
    }

    *e = p->data;

    return OK;
}

/**
 * 获取双向链表第i个元素的结点
 * @param L
 * @param i
 * @return
 */
DuLinkList GetElemP(DuLinkList L, int i) {
    DuLinkList p;
    int count;

    // 校验双向链表存在
    if (L == NULL) {
        return NULL;
    }

    // 位置1~len
    if (i < 1) {
        return NULL;
    }

    p = L;
    count = 0;

    while (p->next != L && count < i) {
        p = p->next;
        count++;
    }

    if (count == i) {
        return p;
    }

    // len+1 指向头结点
    if (count + 1 < i) {
        return NULL;
    }

    return L;
}